#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution
{
    vector<int> parentNode;
    vector<int> depth;
    vector<int> distance;

public:
    vector<int> minimumWeight(vector<vector<int>> &edges, vector<vector<int>> &queries)
    {
        int maxNode = 0;
        map<int, vector<pair<int, int>>> connection;
        for (auto e : edges)
        {
            connection[e[0]].push_back({e[1], e[2]});
            connection[e[1]].push_back({e[0], e[2]});
            maxNode = max(maxNode, max(e[0], e[1]));
        }
        parentNode = vector<int>(maxNode + 1, -1);
        depth = vector<int>(maxNode + 1, 0);
        distance = vector<int>(maxNode + 1, 0);
        dfs(0, -1, connection);
        vector<int> ans(queries.size(), 0);
        for (int i = 0; i < queries.size(); i++)
        {
            ans[i] += distanceBetween(queries[i][0], queries[i][1]);
            ans[i] += distanceBetween(queries[i][0], queries[i][2]);
            ans[i] += distanceBetween(queries[i][1], queries[i][2]);
            ans[i] /= 2;
        }
        return ans;
    }

    void dfs(int node, int parent, map<int, vector<pair<int, int>>> &connection)
    {
        for (auto [child, weight] : connection[node])
        {
            if (child == parent)
                continue;
            depth[child] = depth[node] + 1;
            distance[child] = distance[node] + weight;
            parentNode[child] = node;
            dfs(child, node, connection);
        }
    }

    int distanceBetween(int n1, int n2)
    {
        int lcaNode = lca(n1, n2);
        return distance[n1] + distance[n2] - 2 * distance[lcaNode];
    }

    int lca(int n1, int n2)
    {
        if (depth[n1] > depth[n2])
            swap(n1, n2);
        int diff = depth[n2] - depth[n1];
        for (int i = 0; i < diff; i++)
        {
            n2 = parentNode[n2];
        }
        while(n1 != n2)
        {
            n1 = parentNode[n1];
            n2 = parentNode[n2];
        }
        return n1;
    }
};
int main()
{
    cout << "Code3553" << endl;
    Solution s;
    // vector<vector<int>> edges = {{0, 1, 2}, {1, 2, 3}, {1, 3, 5}, {1, 4, 4}, {2, 5, 6}};
    vector<vector<int>> edges = {{1, 2, 5}, {0, 1, 8}, {0, 4, 7}, {3, 4, 3}};
    vector<vector<int>> queries = {{0, 2, 3}};
    vector<int> ans = s.minimumWeight(edges, queries);
    for (auto a : ans)
        cout << a << endl;
    return 0;
}